//
//  ProblemMS08.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/19.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 08.01. 三步问题
 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

 示例1:
  输入：n = 3
  输出：4
  说明: 有四种走法
 
 示例2:
  输入：n = 5
  输出：13
 
 提示:
 n范围在[1, 1000000]之间

 */
@objcMembers class ProblemMS08: NSObject {
    func solution() {
        print(waysToStep(61))
    }
    
    /*
     动态规划
     1: 创建一个数组dp[len]
     2: dp[i]以i结尾最大的方法数
     3: dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
     */
    func waysToStep(_ n: Int) -> Int {
        if n <= 1 {
            return 1
        }
        if n == 2 {
            return 2
        }
        
        var dp = Array(repeating: 0, count: n+1)
        dp[0] = 1
        dp[1] = 1
        dp[2] = 2
        for i in 3...n {
            dp[i] = (dp[i-1] % 1000000007 + dp[i-2] % 1000000007 + dp[i-3] % 1000000007)  % 1000000007
        }
        
        print(dp)
        return dp[n]
    }
    
    /*
     优化：dp[i] 只与 dp[i-1]、 dp[i-2]、dp[i-3]
     */
    func waysToStepClearAlloc(_ n: Int) -> Int {
        if n <= 1 {
            return 1
        }
        if n == 2 {
            return 2
        }
        
        var fir = 1
        var sec = 1
        var thi = 2
        for i in 3...n {
            let temp = (thi % 1000000007 + sec % 1000000007 + fir % 1000000007)  % 1000000007
            fir = sec
            sec = thi
            thi = temp
        }
        
        return thi
    }
}
